Matemáticas Discretas: Las bases del conteo

Contar es el arte de determinar el tamaño de conjuntos finitos sin el tedioso trabajo de enumeración física. Al aprovechar estructuras lógicas, podemos resolver problemas que van desde combinaciones simples de menús hasta permutaciones criptográficas complejas.

La lógica del "O" y el "Y"

Dos pilares sustentan todo el campo de la combinatoria. Su aplicación depende totalmente de si vemos una tarea como una única elección entre múltiples categorías o como una secuencia de elecciones.

El principio de adición (regla de suma)

Si un conjunto $X$ se divide en subconjuntos disjuntos $X_1, X_2, \dots, X_n$, entonces el número total de elementos $|X|$ es la suma de los tamaños de esos subconjuntos:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Analogía: Elegir una comida en Kay's Quick Lunch eligiendo un sándwich del menú de platos principales O un aperitivo del menú de aperitivos. No puedes tener ambos; eliges un solo artículo.

El principio de multiplicación (regla del producto)

Si una actividad consta de $t$ pasos sucesivos, donde el paso $i$ tiene $n_i$ resultados posibles, el número total de formas de completar la tarea es el producto de las posibilidades en cada paso:

$$N = n_1 \times n_2 \times \dots \times n_t$$

Analogía: Configurar un camión "Big Pickup". Debes elegir un motor (5 opciones) Y un estilo de cabaña (3 opciones). El número total de configuraciones es $5 \times 3 = 15$.

Implementación en código y complejidad

En informática, estos principios se manifiestan en estructuras de bucles. Los bucles secuenciales representan el principio de adición, mientras que los bucles anidados representan el principio de multiplicación.

// Principio de adición (m + n ejecuciones)

para i = 1 hasta m: imprimirln(i)

para j = 1 hasta n: imprimirln(j)

// Principio de multiplicación (m * n ejecuciones)

para i = 1 hasta m:

para j = 1 hasta n:

imprimirln(i, j)

🎯 Principio fundamental

Distinga por palabras clave: "O" significa adición (elecciones mutuamente excluyentes), mientras que "Y" o "sucesivos" significan multiplicación (pasos independientes en una secuencia).

PREGUNTA 1

¿Cuántas comidas en Kay's Quick Lunch (Figura 6.1.1) consisten en un aperitivo y una bebida, suponiendo que hay 3 aperitivos y 4 bebidas?

PREGUNTA 2

En el fragmento de código proporcionado, ¿cuántas veces se ejecutan las instrucciones de impresión en total? [Código: para i = 1 hasta m, imprimirln(i), para j = 1 hasta n, imprimirln(j)]

m × n

$m + n$

$m^n$

$n^m$

PREGUNTA 3

¿Cuántas cadenas de longitud 3 se pueden formar usando las letras {A, B, C, D, E} si se permiten repeticiones?

125

243

PREGUNTA 4

Utilizando la clave pública (n=713, e=29), ¿cuál es la cifra del mensaje M = 333?

333

557

128

712

PREGUNTA 5

¿Cuántas cadenas de longitud 3 usando las letras {A, B, C, D, E} contienen la letra A al menos una vez (permitidas repeticiones)?

125

Desafío: Razonamiento combinatorio avanzado

Camiones, triángulos y palomares

Escenario: Los camiones grandes atraen porque parecen tener infinidad de formas de personalización. Un artículo del New York Times sugiere que necesitas habilidades matemáticas como las de Will Hunting para calcular las configuraciones. Analicemos un modelo con 5 opciones de motores (3.9L V6, 5.2L V8, 5.9L V8, 5.9L turbodiesel, 8L V10).

Defina orden lexicográfico y explique por qué es útil en estructuras de conteo.

Solución: El orden lexicográfico es una generalización del orden alfabético de las palabras en un diccionario a secuencias de símbolos ordenados. Dadas dos secuencias $a_1...a_n$ y $b_1...b_n$, decimos que $a < b$ si en el primer índice $i$ donde $a_i \neq b_i$, tenemos $a_i < b_i$. Es útil porque proporciona un método sistemático para listar todas las permutaciones o combinaciones sin omitir ni repetir ninguna.

¿Qué es una permutación de $x_1, \dots, x_n$? Proporcione una definición formal.

Solución: Una permutación de un conjunto de objetos distintos es un arreglo ordenado de estos objetos. Para un conjunto de $n$ elementos, una permutación es una biyección del conjunto $\{1, 2, \dots, n\}$ al propio conjunto, donde el orden de los elementos en la secuencia resultante importa.

Demuestre que si se eligen cinco cartas de una baraja ordinaria de 52 cartas, al menos dos cartas son del mismo palo.

Solución: Esto es una aplicación del Principio del palomar. Hay 4 palos posibles (los "palomares") y se eligen 5 cartas (los "palomas"). Como $5 > 4$, por el principio del palomar, al menos un palo debe contener $\lceil 5/4 \rceil = 2$ cartas. Por tanto, al menos dos cartas deben compartir un palo.

¿De cuántas formas podemos seleccionar ocho pelotas de una bolsa que contiene pelotas rojas, azules y amarillas (al menos 8 de cada color)? (Dificultad: Palabras clave: 18, Longitud: Corta)

Solución: Este es un problema de combinaciones con repetición. Usando la fórmula de estrellas y barras $C(n+r-1, r)$ donde $n=3$ categorías y $r=8$ selecciones: $C(3+8-1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ formas.